//CArray from MFC afxtempl.h
//List.h
#include <new.h>

#pragma once

/////////////////////////////////////////////////////////////////////////////
// CArray<TYPE, ARG_TYPE>

template<class TYPE, class ARG_TYPE = const TYPE&>
class CArray
{
public:
// Construction
	CArray();

// Attributes
	INT_PTR GetSize() const;
	INT_PTR GetCount() const;
	BOOL IsEmpty() const;
	INT_PTR GetUpperBound() const;
	void SetSize(INT_PTR nNewSize, INT_PTR nGrowBy = -1);

// Operations
	// Clean up
	void FreeExtra();
	void RemoveAll();

	// Accessing elements
	const TYPE& GetAt(INT_PTR nIndex) const;
	TYPE& GetAt(INT_PTR nIndex);
	void SetAt(INT_PTR nIndex, ARG_TYPE newElement);
	const TYPE& ElementAt(INT_PTR nIndex) const;
	TYPE& ElementAt(INT_PTR nIndex);

	// Direct Access to the element data (may return NULL)
	const TYPE* GetData() const;
	TYPE* GetData();

	// Potentially growing the array
	void SetAtGrow(INT_PTR nIndex, ARG_TYPE newElement);
	INT_PTR Add(ARG_TYPE newElement);
	INT_PTR Append(const CArray& src);
	void Copy(const CArray& src);

	// overloaded operator helpers
	const TYPE& operator[](INT_PTR nIndex) const;
	TYPE& operator[](INT_PTR nIndex);

	// Operations that move elements around
	void InsertAt(INT_PTR nIndex, ARG_TYPE newElement, INT_PTR nCount = 1);
	void RemoveAt(INT_PTR nIndex, INT_PTR nCount = 1);
	void InsertAt(INT_PTR nStartIndex, CArray* pNewArray);

// Implementation
protected:
	TYPE* m_pData;   // the actual array of data
	INT_PTR m_nSize;     // # of elements (upperBound - 1)
	INT_PTR m_nMaxSize;  // max allocated
	INT_PTR m_nGrowBy;   // grow amount

public:
	~CArray();
};

/////////////////////////////////////////////////////////////////////////////
// CArray<TYPE, ARG_TYPE> inline functions

template<class TYPE, class ARG_TYPE>
inline INT_PTR CArray<TYPE, ARG_TYPE>::GetSize() const
	{ return m_nSize; }
template<class TYPE, class ARG_TYPE>
inline INT_PTR CArray<TYPE, ARG_TYPE>::GetCount() const
	{ return m_nSize; }
template<class TYPE, class ARG_TYPE>
inline BOOL CArray<TYPE, ARG_TYPE>::IsEmpty() const
	{ return m_nSize == 0; }
template<class TYPE, class ARG_TYPE>
inline INT_PTR CArray<TYPE, ARG_TYPE>::GetUpperBound() const
	{ return m_nSize-1; }
template<class TYPE, class ARG_TYPE>
inline void CArray<TYPE, ARG_TYPE>::RemoveAll()
	{ SetSize(0, -1); }
template<class TYPE, class ARG_TYPE>
inline TYPE& CArray<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex)
{ 
	return m_pData[nIndex]; 
}
template<class TYPE, class ARG_TYPE>
inline const TYPE& CArray<TYPE, ARG_TYPE>::GetAt(INT_PTR nIndex) const
{
	return m_pData[nIndex]; 
}
template<class TYPE, class ARG_TYPE>
inline void CArray<TYPE, ARG_TYPE>::SetAt(INT_PTR nIndex, ARG_TYPE newElement)
{ 
	m_pData[nIndex] = newElement; 
}
template<class TYPE, class ARG_TYPE>
inline const TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(INT_PTR nIndex) const
{ 
	return m_pData[nIndex]; 
}
template<class TYPE, class ARG_TYPE>
inline TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(INT_PTR nIndex)
{ 
	return m_pData[nIndex]; 
}
template<class TYPE, class ARG_TYPE>
inline const TYPE* CArray<TYPE, ARG_TYPE>::GetData() const
	{ return (const TYPE*)m_pData; }
template<class TYPE, class ARG_TYPE>
inline TYPE* CArray<TYPE, ARG_TYPE>::GetData()
	{ return (TYPE*)m_pData; }
template<class TYPE, class ARG_TYPE>
inline INT_PTR CArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
	{ INT_PTR nIndex = m_nSize;
		SetAtGrow(nIndex, newElement);
		return nIndex; }
template<class TYPE, class ARG_TYPE>
inline const TYPE& CArray<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex) const
	{ return GetAt(nIndex); }
template<class TYPE, class ARG_TYPE>
inline TYPE& CArray<TYPE, ARG_TYPE>::operator[](INT_PTR nIndex)
	{ return ElementAt(nIndex); }

/////////////////////////////////////////////////////////////////////////////
// CArray<TYPE, ARG_TYPE> out-of-line functions

template<class TYPE, class ARG_TYPE>
CArray<TYPE, ARG_TYPE>::CArray()
{
	m_pData = NULL;
	m_nSize = m_nMaxSize = m_nGrowBy = 0;
}

template<class TYPE, class ARG_TYPE>
CArray<TYPE, ARG_TYPE>::~CArray()
{
	if (m_pData != NULL)
	{
		for( int i = 0; i < m_nSize; i++ )
			(m_pData + i)->~TYPE();
		delete[] (BYTE*)m_pData;
	}
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::SetSize(INT_PTR nNewSize, INT_PTR nGrowBy)
{
	if (nGrowBy >= 0)
		m_nGrowBy = nGrowBy;  // set new size

	if (nNewSize == 0)
	{
		// shrink to nothing
		if (m_pData != NULL)
		{
			for( int i = 0; i < m_nSize; i++ )
				(m_pData + i)->~TYPE();
			delete[] (BYTE*)m_pData;
			m_pData = NULL;
		}
		m_nSize = m_nMaxSize = 0;
	}
	else if (m_pData == NULL)
	{
		// create buffer big enough to hold number of requested elements or
		// m_nGrowBy elements, whichever is larger.
		size_t nAllocSize = __max(nNewSize, m_nGrowBy);
		m_pData = (TYPE*) new BYTE[(size_t)nAllocSize * sizeof(TYPE)];
		memset((void*)m_pData, 0, (size_t)nAllocSize * sizeof(TYPE));
		for( int i = 0; i < nNewSize; i++ )
#pragma push_macro("new")
#undef new
			::new( (void*)( m_pData + i ) ) TYPE;
#pragma pop_macro("new")
		m_nSize = nNewSize;
		m_nMaxSize = nAllocSize;
	}
	else if (nNewSize <= m_nMaxSize)
	{
		// it fits
		if (nNewSize > m_nSize)
		{
			// initialize the new elements
			memset((void*)(m_pData + m_nSize), 0, (size_t)(nNewSize-m_nSize) * sizeof(TYPE));
			for( int i = 0; i < nNewSize-m_nSize; i++ )
#pragma push_macro("new")
#undef new
				::new( (void*)( m_pData + m_nSize + i ) ) TYPE;
#pragma pop_macro("new")
		}
		else if (m_nSize > nNewSize)
		{
			// destroy the old elements
			for( int i = 0; i < m_nSize-nNewSize; i++ )
				(m_pData + nNewSize + i)->~TYPE();
		}
		m_nSize = nNewSize;
	}
	else
	{
		// otherwise, grow array
		nGrowBy = m_nGrowBy;
		if (nGrowBy == 0)
		{
			// heuristically determine growth when nGrowBy == 0
			//  (this avoids heap fragmentation in many situations)
			nGrowBy = m_nSize / 8;
			nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
		}
		INT_PTR nNewMax;
		if (nNewSize < m_nMaxSize + nGrowBy)
			nNewMax = m_nMaxSize + nGrowBy;  // granularity
		else
			nNewMax = nNewSize;  // no slush

		TYPE* pNewData = (TYPE*) new BYTE[(size_t)nNewMax * sizeof(TYPE)];

		// copy new data from old
		memcpy(pNewData, m_pData, (size_t)m_nSize * sizeof(TYPE));

		// construct remaining elements
		memset((void*)(pNewData + m_nSize), 0, (size_t)(nNewSize-m_nSize) * sizeof(TYPE));
		for( int i = 0; i < nNewSize-m_nSize; i++ )
#pragma push_macro("new")
#undef new
			::new( (void*)( pNewData + m_nSize + i ) ) TYPE;
#pragma pop_macro("new")

		// get rid of old stuff (note: no destructors called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nSize = nNewSize;
		m_nMaxSize = nNewMax;
	}
}

template<class TYPE, class ARG_TYPE>
INT_PTR CArray<TYPE, ARG_TYPE>::Append(const CArray& src)
{
	INT_PTR nOldSize = m_nSize;
	SetSize(m_nSize + src.m_nSize);
	CopyElements<TYPE>(m_pData + nOldSize, src.m_pData, src.m_nSize);
	return nOldSize;
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::Copy(const CArray& src)
{
	if(this != &src)
	{
		SetSize(src.m_nSize);
		CopyElements<TYPE>(m_pData, src.m_pData, src.m_nSize);
	}
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::FreeExtra()
{
	if (m_nSize != m_nMaxSize)
	{
		// shrink to desired size
		TYPE* pNewData = NULL;
		if (m_nSize != 0)
		{
			pNewData = (TYPE*) new BYTE[m_nSize * sizeof(TYPE)];
			// copy new data from old
			memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
		}

		// get rid of old stuff (note: no destructors called)
		delete[] (BYTE*)m_pData;
		m_pData = pNewData;
		m_nMaxSize = m_nSize;
	}
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::SetAtGrow(INT_PTR nIndex, ARG_TYPE newElement)
{
	if (nIndex >= m_nSize)
		SetSize(nIndex+1, -1);
	m_pData[nIndex] = newElement;
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::InsertAt(INT_PTR nIndex, ARG_TYPE newElement, INT_PTR nCount /*=1*/)
{
	if (nIndex >= m_nSize)
	{
		// adding after the end of the array
		SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
	}
	else
	{
		// inserting in the middle of the array
		INT_PTR nOldSize = m_nSize;
		SetSize(m_nSize + nCount, -1);  // grow it to new size
		// destroy intial data before copying over it
		for( int i = 0; i < nCount; i++ )
			(m_pData + nOldSize + i)->~TYPE();
		// shift old data up to fill gap
		memmove(m_pData + nIndex + nCount, m_pData + nIndex, (nOldSize-nIndex) * sizeof(TYPE));

		// re-init slots we copied from
		memset((void*)(m_pData + nIndex), 0, (size_t)nCount * sizeof(TYPE));
		for( int i = 0; i < nCount; i++ )
#pragma push_macro("new")
#undef new
			::new( (void*)( m_pData + nIndex + i ) ) TYPE;
#pragma pop_macro("new")
	}

	// insert new value in the gap
	while (nCount--)
		m_pData[nIndex++] = newElement;
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::RemoveAt(INT_PTR nIndex, INT_PTR nCount)
{
	INT_PTR nUpperBound = nIndex + nCount;

	// just remove a range
	INT_PTR nMoveCount = m_nSize - (nUpperBound);
	for( int i = 0; i < nCount; i++ )
		(m_pData + nIndex + i)->~TYPE();
	if (nMoveCount)
	{
		memmove(m_pData + nIndex, m_pData + nUpperBound, (size_t)nMoveCount * sizeof(TYPE));
	}
	m_nSize -= nCount;
}

template<class TYPE, class ARG_TYPE>
void CArray<TYPE, ARG_TYPE>::InsertAt(INT_PTR nStartIndex, CArray* pNewArray)
{
	if (pNewArray->GetSize() > 0)
	{
		InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
		for (INT_PTR i = 0; i < pNewArray->GetSize(); i++)
			SetAt(nStartIndex + i, pNewArray->GetAt(i));
	}
}

template<class TYPE>
inline void CopyElements(TYPE* pDest, const TYPE* pSrc, INT_PTR nCount)
{
	// default is element-copy using assignment
	while (nCount--)
		*pDest++ = *pSrc++;
}

template<class ITEM, class DATA>
class List
{
protected:
	struct Node
	{
		ITEM item;
		DATA data;
	};
public:
// Construction
	/* explicit */ List();

// Attributes
	// count of elements
	INT_PTR GetCount() const;

// Operations
	// add an element
	INT_PTR Add(ITEM& item, DATA& data);

	// remove all elements
	void Clear();

	// getting/modifying an element at a given position
	ITEM& Get(INT_PTR position);
	const ITEM& Get(INT_PTR position) const;
	DATA& GetData(INT_PTR position);
	const DATA& GetData(INT_PTR position) const;
	void Set(INT_PTR position, ITEM& item, DATA& data);
	void SetData(INT_PTR position, DATA& data);

	// overloaded operator helpers
	const ITEM& operator[](INT_PTR nIndex) const;
	ITEM& operator[](INT_PTR nIndex);

	// Operations that move elements around
	void Remove(INT_PTR position);
	void Insert(INT_PTR position, ITEM& item, DATA& data);

	// helper functions (note: O(n) speed)
	INT_PTR IndexOf(ITEM& item, INT_PTR start = 0) const;
		// defaults to starting at the HEAD, return -1 if not found

// Implementation
protected:
	CArray<Node, Node&>* m_pList;

public:
	~List();
};

/////////////////////////////////////////////////////////////////////////////
// CList<TYPE, ARG_TYPE> inline functions

template<class ITEM, class DATA>
inline INT_PTR List<ITEM, DATA>::GetCount() const
	{ return m_pList->GetCount(); }
template<class ITEM, class DATA>
inline ITEM& List<ITEM, DATA>::Get(INT_PTR position)
	{ return m_pList->GetAt(position).item; }
template<class ITEM, class DATA>
inline DATA& List<ITEM, DATA>::GetData(INT_PTR position)
	{ return m_pList->GetAt(position).data; }
template<class ITEM, class DATA>
inline const ITEM& List<ITEM, DATA>::Get(INT_PTR position) const
	{ return m_pList->ElementAt(position).item; }
template<class ITEM, class DATA>
inline const DATA& List<ITEM, DATA>::GetData(INT_PTR position) const
	{ return m_pList->ElementAt(position).data; }
template<class ITEM, class DATA>
inline void List<ITEM, DATA>::Set(INT_PTR pos, ITEM& item, DATA& data)
	{ Node* pNode = &(m_pList->GetAt(pos));
		pNode->item = item;
		pNode->data = data; }
template<class ITEM, class DATA>
inline void List<ITEM, DATA>::SetData(INT_PTR pos, DATA& data)
	{ Node* pNode = &(m_pList->GetAt(pos));
		pNode->data = data; }
template<class ITEM, class DATA>
inline const ITEM& List<ITEM, DATA>::operator[](INT_PTR nIndex) const
	{ return m_pList->GetAt(nIndex); }
template<class ITEM, class DATA>
inline ITEM& List<ITEM, DATA>::operator[](INT_PTR nIndex)
	{ return m_pList->ElementAt(nIndex); }
template<class ITEM, class DATA>
inline INT_PTR List<ITEM, DATA>::Add(ITEM& item, DATA& data)
	{ Node node = {item, data};
		return m_pList->Add(node); }
template<class ITEM, class DATA>
inline void List<ITEM, DATA>::Clear()
	{ m_pList->RemoveAll(); }
template<class ITEM, class DATA>
inline void List<ITEM, DATA>::Remove(INT_PTR position)
	{ m_pList->RemoveAt(position); }
template<class ITEM, class DATA>
inline void List<ITEM, DATA>::Insert(INT_PTR position, ITEM& item, DATA& data)
	{ Node node = {item, data};
		m_pList->InsertAt(position, node); }

template<class ITEM, class DATA>
INT_PTR List<ITEM, DATA>::IndexOf(ITEM& item, INT_PTR start) const
{
	for(INT_PTR k = start; k < m_pList->GetCount(); k++)
		if (m_pList->GetAt(k).item == item)
			return k;
	return -1;
}

template<class ITEM, class DATA>
List<ITEM, DATA>::List()
{
	m_pList = new CArray<Node, Node&>();
}

template<class ITEM, class DATA>
List<ITEM, DATA>::~List()
{
	Clear();
	delete m_pList;
}

